//
// Description: 5929. 处理含限制条件的好友请求
// Created by Loading on 2021/11/14.
//

#include <bits/stdc++.h>

using namespace std;

/* 并查集 */
vector<bool> friendRequests(int n, vector<vector<int>> &restrictions, vector<vector<int>> &requests) {
    // 父节点
    vector<int> father(n);
    // 初始化，每个节点的父节点是本身
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }

    // 寻找父节点
    auto findFather = [&](int x) {
        /* 功能：找到元素x在该集合中的根节点（根节点满足x == father[x]） */

        // 记录初始节点
        int a = x;
        // 循环查找父节点，找到集合的根节点
        while (x != father[x]) {
            x = father[x];   // 循环结束后的 x 为该集合的根节点
        }
        /* 路径压缩，将寻找根节点路途中的每个节点指向其根节点，优化之后的查找速度，可不写 */
        while (a != father[a]) {
            int b = a;      // 记录 a，防止后面被覆盖
            a = father[a];  // 让 a 指向其父节点
            father[b] = x;  // 指向根节点
        }
        return x;
    };

    // 朋友名单
    vector<unordered_set<int>> friends(n);
    // 限制加入名单
    vector<unordered_set<int>> restricts(n);
    // 名单初始化
    for (int i = 0; i < n; ++i) {
        friends[i].insert(i);
    }
    for (auto v : restrictions) {
        restricts[v[0]].insert(v[1]);
        restricts[v[1]].insert(v[0]);
    }

    vector<bool> res;
    for (auto v : requests) {
        // 找到两者的父节点
        int f1 = findFather(v[0]);
        int f2 = findFather(v[1]);
        bool flag = true;
        for (auto x : friends[f2]) {
            // f1 的限制名单中存在 f2 的朋友，false 结束
            if (restricts[f1].find(x) != restricts[f1].end()) {
                flag = false;
                break;
            }
        }
        res.emplace_back(flag);
        if (flag) {
            // 请求好友成功，将 f2 的限制名单和朋友名单加入 f1，
            restricts[f1].insert(restricts[f2].begin(), restricts[f2].end());
            friends[f1].insert(friends[f2].begin(), friends[f2].end());
            // f2 的父节点指向 f1
            father[f2] = f1;
        }
    }

    return res;
}

int main() {
    int n = 3;
    vector<vector<int>> restrictions = {{0, 1}};
    vector<vector<int>> requests = {{0, 2},
                                    {2, 1}};
    vector<bool> res = friendRequests(n, restrictions, requests);
    for (auto b : res) {
        cout << b << ' ';
    }
    cout << endl;

    return 0;
}